package com.leetcode.algorithm.y22.m07.w4;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

/**
 * 380. O(1) 时间插入、删除和获取随机元素
 * 
 * https://leetcode.cn/problems/insert-delete-getrandom-o1/
 * 
 * @author jie.deng
 *
 */
class RandomizedSet {

	private List<Integer> list;
	private Map<Integer, Integer> map;
	private Random random;

	public RandomizedSet() {
		random = new Random();
		list = new ArrayList<>();
		map = new HashMap<>();
	}

	public boolean insert(int val) {
		if (map.containsKey(val)) {
			return false;
		}
		list.add(val);
		map.put(val, list.size() - 1);
		return true;
	}

	public boolean remove(int val) {
		if (!map.containsKey(val)) {
			return false;
		}
		int idx = map.remove(val).intValue();
		list.remove(idx);
		return true;
	}

	public int getRandom() {
		int idx = random.nextInt(list.size());
		return list.get(idx);
	}
}